//
//  Problem220.swift
//  LeetCode
//
//  Created by 武侠 on 2023/6/28.
//  Copyright © 2023 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 220. 存在重复元素 III 困难
 
 给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。
 找出满足下述条件的下标对 (i, j)：
     i != j,
     abs(i - j) <= indexDiff
     abs(nums[i] - nums[j]) <= valueDiff
 如果存在，返回 true ；否则，返回 false 。

 示例 1：
     输入：nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
     输出：true
     解释：可以找出 (i, j) = (0, 3) 。
     满足下述 3 个条件：
     i != j --> 0 != 3
     abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
     abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0
 示例 2：
     输入：nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
     输出：false
     解释：尝试所有可能的下标对 (i, j) ，均无法满足这 3 个条件，因此返回 false 。
  
 提示：
 2 <= nums.length <= 105
 -109 <= nums[i] <= 109
 1 <= indexDiff <= nums.length
 0 <= valueDiff <= 109
 */
class Problem220: NSObject {
    /*
     思路： 滑动窗口
     题目要求符合的条件：
     1: n - valueDiff <= value <= n + valueDiff
     2: i - valueDiff <= index <= i + valueDiff
     3: i != index
     在这里可以优化的是：第2个条件，变成：i - valueDiff < index；删除后面的原因是在：在（i+1 ～ i+valueDiff)这些索引位置的前半部分也要判断一次，所以可以删除
     步骤：
     1: 遍历数组，寻找所有 (i-indexDiff ~ i) 这些位置的值：条件2和条件3
     2: 判断这些值是否在符合：条件1
     */
    func containsNearbyAlmostDuplicate(_ nums: [Int], _ indexDiff: Int, _ valueDiff: Int) -> Bool {
        // 1: 遍历数组，寻找[i-k ~ i)的元素是否在dic中
        for i in 0..<nums.count {
            let leftIndex = max(0, i-indexDiff)
            for j in leftIndex..<i {
                // 2: 判断这些值是否在符合：条件1
                if nums[i] - valueDiff <= nums[j], nums[j] <= nums[i] + valueDiff {
                    return true
                }
            }
        }
        
        return false
    }
    
    /*
     思路：桶排序
     题目要求符合的条件：
     1: n - valueDiff <= value <= n + valueDiff
     2: i - valueDiff <= index；不需要右边的判断条件
     3: i != index
     
     设计一个桶：
     1: 首先确认一个桶的大小，这里直接使用t = valueDiff+1即可, +1是为了防止valueDiff = 0
     2: 确认当前元素n，在哪个桶里面
                                             n
     ----t+2------t+1------t------0------t------t+1------t+2----
     3: 那么符合‘条件1’的value只能在3个位置：
        3.1: 和n在一个桶里面
        3.2: 在n所在的桶的左边的桶，而且还要满足 n - value < t
        3.3: 在n所在的桶的右边的桶，而且还要满足 value - n < t
     4: 那么满足‘条件2’和‘条件3’，创建一个字典：只存储(i-indexDiff ~ i)这些位置所对应的桶
     */
    func containsNearbyAlmostDuplicateTong(_ nums: [Int], _ indexDiff: Int, _ valueDiff: Int) -> Bool {
        
        // 桶
        var dic:[Int: Int] = [:]
        
        for i in 0..<nums.count {
            // 1: 求出当前nums[i]在桶的位置
            let index = indexOfTong(nums[i], valueDiff+1)
            
            print(i, nums[i], index, dic)
            // 条件 3.1
            if dic[index] != nil {
                return true
            }
            // 条件 3.2
            if dic[index-1] != nil, nums[i] - dic[index-1]! <= valueDiff {
                return true
            }
            
            // 条件 3.2
            if dic[index+1] != nil, dic[index+1]! - nums[i] <= valueDiff {
                return true
            }
            
            // 把当前位置插入到桶中，方便后面i+1位置计算
            dic[index] = nums[i]
            
            // 删除i-indexDiff的位置的
            if i - indexDiff >= 0, i - indexDiff != i {
                let lastIndex = indexOfTong(nums[i - indexDiff], valueDiff+1)
                if dic[lastIndex] != nil {
                    dic.removeValue(forKey: lastIndex)
                }
            }
        }
        
        return false
    }
    
    // 如果判断num<0的时候要-1，是因为 -2/5 也是0，2/5也是0，所以负数往后移动一位
    func indexOfTong(_ num: Int, _ t: Int) -> Int {
        return num < 0 ? num / t - 1 : num / t
    }
}
